package com.adee.algorithm.test.template;

import lombok.Data;

import java.util.Arrays;

public class BinaryTree {
    public static void main(String[] args) {
        int[] arr = {35,10,78,1,22,30,85,100,5,20,18,69,77};
        Node root = buildBinaryTree(arr);
        System.out.println("源数组：");
        printArr(arr);
//        System.out.println("先序遍历：");
        preSort(root);
        preSortR(root);
        System.out.println();
        midSort(root);
        midSortR(root);
        System.out.println();
        postSort(root);
        postSortR(root);
    }

    // 构造一个二叉排序树
    public static Node buildBinaryTree(int[] arr) {
        if(arr == null || arr.length == 0) return null;
        Node root = new Node(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            Node node = root;
            while (true) {
                if (arr[i] <= node.getData()) {
                    Node left = node.getLeft();
                    if (left == null) {
                        node.setLeft(new Node(arr[i]));
                        break;
                    }else {
                        node = left;
                    }
                } else {
                    Node right = node.getRight();
                    if (right == null) {
                        node.setRight(new Node(arr[i]));
                        break;
                    }else {
                        node = right;
                    }
                }
            }
        }
        return root;
    }

    // 先序遍历
    public static void preSort(Node root) {
        if (root == null) return;

    }

    // 中序遍历
    public static void midSort(Node root) {
        if (root == null) return;

    }

    // 后序遍历
    public static void postSort(Node root) {
        if (root == null) return;

    }

    // 递归-先序遍历
    public static void preSortR(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.getData() + " ");
        preSortR(node.getLeft());
        preSortR(node.getRight());
    }

    // 递归-中序遍历
    public static void midSortR(Node node) {
        if (node == null) {
            return;
        }
        midSortR(node.getLeft());
        System.out.print(node.getData() + " ");
        midSortR(node.getRight());
    }

    // 递归-后序遍历
    public static void postSortR(Node node) {
        if (node == null) {
            return;
        }
        postSortR(node.getLeft());
        postSortR(node.getRight());
        System.out.print(node.getData() + " ");
    }

    public static void printArr(int[] arr) {
        if (arr == null || arr.length == 0) return;
        Arrays.stream(arr).forEach(i-> System.out.print(i + " "));
        System.out.println();
    }

    @Data
    public static class Node {
        private int data;
        private Node left;
        private Node right;
        public Node(int data) {
            this.data = data;
        }
    }
}
